This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
Elliptic curve cryptography (ECC) is becoming more and more widespread, owing to, among other things, a key length that is significantly shorter than a Rivest-Shamir-Adleman (RSA) key for a corresponding security level. However, shorter key length is not the only factor to consider when choosing a cryptosystem; for example computation time must also be considered, as a relatively long wait may prove irritating to a user that uses a cryptographic system.
While elliptic curve cryptography may be used in practically any situation, it is particularly suitable for use in embedded devices as ECC requires less memory and computing capabilities than RSA-based cryptography.
The basic operation for elliptic curve cryptography is the scalar multiplication: given a point P on an elliptic curve and a scalar d, one has to compute point Q=dP (that is, P+P+ . . . +P, d times). There exist two main families of scalar multiplication methods, depending on in which direction the scalar d is scanned:                left-to-right methods, and        right-to-left methods.        
Left-to-right methods are often used as they give rise to better performance, but they are also known to offer a lower security level.
Up until now, the skilled person has, to a certain extent, been forced to choose between performance and security. It can thus be appreciated that there is a need for a solution that overcomes at least some of the problems of the prior art. The present invention provides a solution that speeds up prior art right-to-left scalar multiplication so that the difference in performance between the two families decreases.
The classical prior art right-to-left based scalar multiplication methods will now be described.
Let E denote an elliptic curve over a field K of characteristic≠2, 3. Such an elliptic curve can be given by a Weierstrass equation:E/K:Y2=X3+aXZ4+bZ6.
The set of points (X, Y, Z) on the elliptic curve forms an abelian group where the neutral element, called the point at infinity, is O=(1, 1, 0). The projective point (X, Y, Z) corresponds to O if Z=0 and to the affine point (X/Z2, Y/Z3) otherwise. Note that the projective coordinates of a projective point are not unique because (X, Y, Z)=(t2X, t3Y, tZ) for every nonzero t in K.
The classical prior art right-to-left binary scalar multiplication method takes as input a scalar d≧0 and a point P=(X, Y, Z) on an elliptic curve E with parameters a and b, and outputs the point Q=dP.
Input: d, P=(X, Y, Z)
Output: dP=(X*, Y*, Z*)
Method:
1. If d=0 or Z=0 then return (1, 1, 0) and stop.
2. Set (X*, Y*, Z*)←(1, 1, 0) and (T1, T2, T3)←(X, Y, Z)
3. While (d≧1) do                a. If (d is odd) then                    i. d←d−1            ii. (X*, Y*, Z*)←Add[(X*, Y*, Z*), (T1, T2, T3)]                        b. d←d/2        c. (T1, T2, T3)←Double[(T1, T2, T3)]        
4. Return (X*, Y*, Z*)
The classical prior art NAF (Non-Adjacent Form)-based scalar multiplication method takes as input a scalar d≧0 and a point P=(X, Y, Z) on an elliptic curve E with parameters a and b, and outputs the point Q=dP.
Input: d, P=(X, Y, Z)
Output: dP=(X*, Y*, Z*)
Method:
1. If d=0 or Z=0 then return (1, 1, 0) and stop.
2. Set (X*, Y*, Z*)←(1, 1, 0) and (T1, T2, T3)←(X, Y, Z)
3. While (d≧1) do                a. If (d is odd) then                    i. u←2−(d mod 4)            ii. d←d−u            iii. if (u=1) then (X*, Y*, Z*)←Add[(X*, Y*, Z*), (T1, T2, T3)]            iv. if (u=−1) then (X*, Y*, Z*)←Add[(X*, Y*, Z*), (T1, −T2, T3)]                        b. d←d/2        c. (T1, T2, T3)←Double[(T1, T2, T3)]        
4. Return (X*, Y*, Z*)